package Leetcode;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/n-queens/
 *
 * 看这个讲解
 * https://leetcode-cn.com/problems/n-queens/solution/hui-su-suan-fa-xiang-jie-by-labuladong/
 */
public class L52_NQueensII {
    int res;
    int length;
    public int totalNQueens(int n) {
        if(n<=0) return 0;
        char[][] board = new char[n][n];length = n;
        for(int i=0; i<n; i++) Arrays.fill(board[i],'.');
        backtrace(board, 0);
        return res;
    }

    private void backtrace(char[][] board, int row){
        //到这一层了，相等的话，这是一个解了
        if (row == board.length) {
            res ++;
            return;
        }
        int n=board.length;
        //开始挑下面节点的选择
        for(int i=0; i<n; i++){
            if(!isValid(board, row, i)) continue;;
            board[row][i] = 'Q';
            backtrace(board, row+1);
            board[row][i] = '.';
        }
    }

    /**
     * 在当前位置，能否放一个Q
     */
    private boolean isValid(char[][] board, int row, int col){
        //遍历当前行，行不用遍历的，因为每行只能放一个，上面已经自动给跳过了
        //for(char t: board[row]) if(t == 'Q') return false;
        //当前竖行
        for(char[] t: board) if(t[col]=='Q') return false;
        //检查左上方是否有
        for(int i=row-1,j=col-1; i>=0 && j>=0; i--,j--) if(board[i][j]=='Q') return false;
        //检查右上方是否有，这里要想清楚，这里踩坑了
        for(int i=row-1,j=col+1; i>=0 && j>=0; i--,j++) if(board[i][j]=='Q') return false;
        return true;
    }


}
